#include <algorithm>
#include<bits/stdc++.h>
using namespace std;
#define maxn 101

typedef struct
{
    int vexnum,edgenum;
    int vex[maxn];
    int edge[maxn][maxn];
}AMGrpah;
int dis[maxn][maxn];
int p[maxn][maxn];
int findIndex(AMGrpah g,int u)
{
    for(int i = 0;i <g.vexnum;i++)
    {
        if(u==g.vex[i])
        {
            return i;
        }
    }
    return -1;
}

void createG(AMGrpah &g)
{
    cout<<"请输入节点个数"<<endl;
    cin>>g.vexnum;
    cout<<"请输入边的个数"<<endl;
    cin>>g.edgenum;
    cout<<"请输入每个节点的信息"<<endl;
    for(int i = 0;i < g.vexnum;i++)
    {
        cin>>g.vex[i];
    }
    for(int i = 0;i <g.vexnum;i++)
    {
        for(int j = 0;j <g.vexnum;j++)
        {
            if(i!=j)
            {
                g.edge[i][j]=0x3f3f3f3f;
            }
            else {
                g.edge[i][j] = 0;
            }
        }
    }
    for(int i = 0;i <g.edgenum;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        int k,s;
        k = findIndex(g,u);
        s = findIndex(g,v);
        if(k!=-1&&s!=-1)
        {
            g.edge[k][s] = w;
        }
    }
}

void floyd(AMGrpah &g)
{
    int i,j,k;
    for(i = 0;i <g.vexnum;i++)
    {
        for(j = 0;j < g.vexnum;j++)
        {
            dis[i][j] = g.edge[i][j];
            if(dis[i][j]<0x3f3f3f3f&&i!=j)
            {
                p[i][j] = i;
            }
            else {
                p[i][j]=-1;
            }
        }
    }
    for(k = 0;k < g.vexnum;k++)
    {
        for(i = 0;i <g.vexnum;i++)
        {
            for(j = 0;j <g.vexnum;j++)
            {
                if(dis[i][j]>dis[i][k]+dis[k][j])
                {
                    dis[i][j] = dis[i][k]+dis[k][j];
                    p[i][j] = p[k][j];
                }
            }
        }
    }
}